import java.util.HashMap;
import java.util.Map;

/**
 * @author: li_jian
 * @version: 1.0
 * @date: 2020/7/5 22:30
 * @description： @link{https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6?tpId=13&&tqId=11157&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking}
 */
public class JZ_重建二叉树 {

    public static void main(String[] args) {
        JZ_重建二叉树 test = new JZ_重建二叉树();

        test.reConstructBinaryTree(new int[]{3,9,20,15,7 }, new int[]{9,3,15,20,7 });
    }


    //缓存中序遍历数组中每个值对应的索引
    private static Map<Integer, Integer> map = new HashMap<>();

    /**
     * 根据前序和中序遍历重建二叉树:前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}
     *
     * @param pre 前序遍历
     * @param in  中序遍历
     * @return
     */
    public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        for (int i = 0; i < in.length; i++) {
            map.put(in[i], i);
        }

        return reConstructBinaryTree(pre, 0, pre.length - 1, 0);
    }

    /**
     * 递归重建二叉树的方法
     *
     * @param pre  前序遍历的数组
     * @param preL 当前节点在前序遍历中的位置
     * @param preR
     * @param inL
     * @return
     */
    public TreeNode reConstructBinaryTree(int[] pre, int preL, int preR, int inL) {
        if (preL > preR)
            return null;

        // 创建一个节点，如果是第一个就对应的是根节点
        TreeNode root = new TreeNode(pre[preL]);
        // 当前节点在中序遍历的位置
        int inIndex = map.get(root.val);
        // 求当前节点左子树的节点数
        int leftTreeSize = inIndex - inL;
        // 创建当前节点的左孩子
        // preL + 1 左孩子在前序遍历节点中的位置
        // inL => 左孩子在中序遍历中的位置
        root.left = reConstructBinaryTree(pre, preL + 1, preL + leftTreeSize, inL);
        // 创建当前节点的右孩子
        // preL + leftTreeSize + 1 => 右孩子在前序遍历中的位置
        // inL + leftTreeSize + 1  => 右孩子在中序遍历中的位置
        root.right = reConstructBinaryTree(pre, preL + leftTreeSize + 1, preR, inL + leftTreeSize + 1);
        return root;
    }
}

/**
 * Definition for binary tree
 */
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}